package com.maishi.programmer.jainzhioffer;

/**
 * Created by brossdong on 2018/4/14.
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 */
public class TestProblem55_1 {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode (int val) {
            this.val = val;
        }
    }

    /**
     * 如果我们用后序遍历的方式遍历二叉树的每一个结点，
     * 在遍历到一个结点之前我们就已经遍历了它的左右子树。
     * 只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶节点的路径的长度)，
     * 我们就可以一边遍历一边判断每个结点是不是平衡的。
     * @param root
     * @return
     */
    private boolean isBalanced = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        getDepth(root);
        return isBalanced;
    }
    public int getDepth (TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        int right = getDepth(root.right);
        if (Math.abs(left - right) > 1) {
            isBalanced = false;
        }
        return right > left ? right + 1 : left + 1;
    }

}
